package 动态规划.另类的;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/5 18:24
 */
public class lc5最长回文子串 {


    public static void main(String[] args) {


    }

    public boolean recursion(int i,int j,char[] chars){
        if(i > j){
            return true;
        }
        if(chars[i] == chars[j]){
            return recursion(i + 1,j - 1,chars);
        }
        return false;
    }

 // 隐藏的潜在条件就是  i < j     : a b a 其实 三个数, 或者 a a 两个数, 都可以直接返回
    public String dp(String s){
        char[] chars = s.toCharArray();
        boolean dp[][] = new boolean[chars.length + 1][chars.length + 1];
        int ans = 0, l = 0,r = 1;
        for(int i = s.length() - 1;i >=0 ;i--){
            for(int j = i;j < s.length();j++){

                if(chars[i] == chars[j]){
                    if(j - i <= 2 || dp[i + 1][j - 1]){
                        dp[i][j] = true;
                        if(j - i + 1 > ans){
                            l = i;
                            r =  j;
                            ans = j - i + 1;
                        }
                    }
                }
            }
        }
        return s.substring(l,r + 1);
    }

    /*
     没办法一步到位的
     */
    public int recursion2(int i,int j,char[] chars){
        if(i == j){
            return 1;
        }
        if(i > j){
            return 0;
        }
        int ans = Integer.MIN_VALUE;
        if(chars[i] == chars[j]){
            return recursion2(i + 1,j - 1,chars) + 2;
        }
        return ans;
    }


}
